DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.33

Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC

Authors: Ulysse Léchine

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

We give an alternate and simpler proof of the fact that PRAM without bit operations (shortened to iPRAM for integer PRAM) as considered in paper [Mulmuley, 1999] cannot solve the maxflow problem. To do so we consider the model of PRAM working over real number (rPRAM) which is at least as expressive as the iPRAM models when considering integer inputs. We then show that the rPRAM model is as expressive as the algebraic version of NC : algebraic circuits of fan-in 2 and of polylog depth noted NC^alg. We go on to show limitations of the NC^alg model using basic facts from real analysis : those circuits compute low degree piece wise polynomials. Then, using known results we show that the maxflow function is not a low-degree piece-wise polynomial. Finally we argue that NC^alg is actually a really limited class which limits our hope of extending our results to the boolean version of NC.

Cite as

Ulysse Léchine. Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lechine:LIPIcs.FSTTCS.2023.33,
  author =	{L\'{e}chine, Ulysse},
  title =	{{Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.33},
  URN =		{urn:nbn:de:0030-drops-194061},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.33},
  annote =	{Keywords: Algebraic complexity, P vs NC, algebraic NC, GCT program}
}

Search Results

Documents authored by Léchine, Ulysse

Revisiting Mulmuley: Simple Proof That Maxflow Is Not in the Algebraic Version of NC

Abstract

Cite as

Thanks for your feedback!

Could not send message